import java.util.Arrays;

public abstract class SortAlgorithm {
    public void sort(Object[] list){
        this.sortPart(list,0,list.length);
    }

    private void sortPart(Object[] list, int start, int end){
        int length = end-start;
        if(length == 1){
            return;
        } else {
            int mid = (start + end)/2;
            int leftPartLength = mid-start;
            int rightPartLength = end-mid;
            sortPart(list,start,mid);
            sortPart(list,mid,end);
            merge(list,start,mid,end);
        }
    }

    public void merge(Object[] list, int start, int middle, int end){
        int pointer1 = start;
        int pointer2 = middle;

        //复制数组
        Object[] origin = new Object[end-start];
        System.arraycopy(list, start, origin, 0, end-start);

        //归并
        for(int i=0;i<origin.length;i++){
            if(pointer1 < middle && pointer2 < end){
                Object value1 = origin[pointer1-start];
                Object value2 = origin[pointer2-start];
                if(this.lessThan(value1, value2)){
                    list[i+start] = value1;
                    pointer1++;
                } else {
                    list[i+start] = value2;
                    pointer2++;
                }
            } else if(pointer1 < middle){
                list[i+start] = origin[pointer1-start];
                pointer1++;
            } else if(pointer2 < end){
                list[i+start] = origin[pointer2-start];
                pointer2++;
            } else {
                throw new RuntimeException();
            }
        }
    }

    public abstract boolean lessThan(Object a, Object b);
}
